/**
 * Created by sunchenglin on 2017/6/29.
* 小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
*给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
 */
import java.util.*;
public class DP {
        public int getMost(int[][] board) {
            for(int i=0;i<6;i++){
                for(int j=0;j<6;j++){
                    if(i<1 && j>=1){
                        board[i][j] += board[i][j-1];
                    }
                    if(j<1 && i>=1){
                        board[i][j] += board[i-1][j];
                    }
                    if(j>=1 && i>=1){
                        board[i][j] += (board[i][j-1]>board[i-1][j])? board[i][j-1]: board[i-1][j];
                    }
                }
            }
            // write code here
            return board[5][5];
        }
        public static void main(String[] args){
            int[][] board = {
                    {564 ,448 ,654 ,186 ,490 ,699},
                    {487 ,444 ,563 ,228 ,365 ,261},
                    {429 ,505 ,612 ,564 ,715 ,726},
                    {464 ,617 ,234 ,647 ,702 ,263},
                    {245 ,249 ,231 ,462 ,453 ,646},
                    {669 ,510 ,492 ,512 ,622 ,135}
            };
            DP dp = new DP();
            System.out.println(dp.getMost(board));

        }

}
